package com.taldh.algorithm.二分查找法;

import com.taldh.utils.assertutils.AssertUtils;
import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.Collections;

public class BinarySearch {

    /*
     * 循环实现二分查找算法arr 已排好序的数组x 需要查找的数-1 无法查到数据
     */
    public static int binarySearch(int[] nums, int target) {
        int low = 0;
        int high = nums.length-1;
        while(low <= high) {
            int middle = (low + high)/2;
            if(target == nums[middle]) {
                return middle;
            }else if(target <nums[middle]) {
                high = middle - 1;
            }else {
                low = middle + 1;
            }
        }
        return -1;
    }

    public int binarySearch(int[] nums, int target, int start, int end) {
        if (nums == null || nums.length == 0 || end < start) {
            return -1;
        }
        int half = (start + end) / 2;
        if (nums[half] == target) {
            return half;
        } else if (nums[half] > target) {
            return binarySearch(nums,target, start, half-1);
        } else {
            return binarySearch(nums, target, half+1, end);
        }
    }

    public int getCycleSortArrayIndex(int[] nums, int target, int start, int end) {
        if (nums == null || nums.length == 0 || end < start) {
            return -1;
        }
        int half = (start + end) / 2;
        //分三种情况
        if (nums[half] == target) {
            return half;
        } else if (target < nums[half] && target >= nums[start]) {     // 找的数在左边，
            //分两种情况
            //2, nums[start] < nums[half], 意味着左边右边是有序的可以二分查找
            if (nums[start] < nums[half]) {
                return binarySearch(nums, target, start, half);
            } else {
                //3, 意味着左边是cycle sort array ，用现在这个方法查找
                return getCycleSortArrayIndex(nums, target, start, half);
            }
        } else {  //找的数在右边
            //分两种情况
            //2, nums[half] < nums[end], 意味着左边可以二分查找
            if (nums[half] < nums[end]) {
                // 意味着右边是有序的可以二分查找
                return binarySearch(nums, target, half, end);
            } else {
                return getCycleSortArrayIndex(nums, target, half, end);
            }
        }
    }

    public int getCycleSortArrayIndex(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        return getCycleSortArrayIndex(nums, target, 0, nums.length - 1);
    }

    /**
     扭转后的数组，找到指定的数，返回下标，找不到时返回-1
     样例输入：3，4，5，6，7，1，2   查找数字7
     样例输出：4
     **/

    @Test
    public void test2() {
        int[] nums = {3, 4, 5, 6, 7, 1, 2};
        Assert.assertEquals(4, getCycleSortArrayIndex(nums, 7));
    }

    @Test
    public void test5() {
        int[] nums = {3, 4, 5, 6, 7, 1, 2};
        Assert.assertEquals(6, getCycleSortArrayIndex(nums, 2));
    }

    @Test
    public void test3() {
        int[] nums = {3, 4, 5, 6, 7, 8, 9, 10, 1, 2};
        Assert.assertEquals(4, getCycleSortArrayIndex(nums, 7));
    }


    @Test
    public void test4() {
        int[] nums = {8, 9, 10, 1, 2, 3, 4, 5, 6, 7};
        Assert.assertEquals(9, getCycleSortArrayIndex(nums, 7));
    }

    @Test
    public void test() {
        Integer[] nums = {1, 2, 4, 6, 7};
//        Assert.assertEquals(1, binarySearch(nums,2, 0, 5));
        Assert.assertEquals(1, Collections.binarySearch(Arrays.asList(nums), 2));
    }
}
